1. Field of the Invention
The invention relates in general to an apparatus for encryption and decryption, and more particularly to an apparatus for encryption and decryption, capable of use in encryption and decryption of advanced encryption standard (AES).
2. Description of the Related Art
Since the electronic-business (e-business) grows rapidly for the few years and the numbers of on-line transactions are increasing, data encryption is required to be much stricter for the sake of data security. A stricter encryption standard, advanced encryption standard (AES), has been developed after the widely used data encryption standard (DES) and is expected to be replaced for DES so as to fulfil the stricter data security requirement. An AES system is a symmetric-key system in which the sender and receiver of a message share a single, common key, thereafter called a subkey, which is used to encrypt and decrypt the message. The data length of a subkey may be chosen to be any of 128, 192, or 256 bits while a plaintext and a ciphertext can be such as 128 bits. For the sake of simplicity, hereinafter, plaintexts, ciphertexts, and subkeys are chosen to be 128 bits in length.
The AES system encrypts a plaintext according to the following encryption algorithm.
Encryption Algorithm of AESAddRoundKeyfor round=1 to Nr−1KeyExpansionSubBytesShiftRowsMixColumnsAddRoundKeyend forSubBytesShiftRowsAddRoundKey
In this encryption algorithm, a round key addition operation (AddRoundKey) is first to perform a bitwise exclusive-OR (EX-OR) operation on the plaintext and the first subkey and to output the result of the EX-OR operation. Next, the algorithm proceeds to the following looping. The number of rounds of the looping is set to Nr−1 in which Nr is specified according to the AES specification. For each round, a key expansion operation (KeyExpansion) is performed to produce a new subkey based on a previous subkey. That is, in the first round of the looping, the first subkey is used to generate the second subkey by the KeyExpansion. After the KeyExpansion, a byte substitution operation (SubBytes) acts on the result of the AddRoundKey. Next, a row shifting operation (ShiftRows) is performed and then a column mixing operation (MixColumns) acts on the result of the ShiftRows. The first round is ended by performing the EX-OR operation on the result of the MixColumns and the current subkey, i.e., the second subkey. The looping are executed for the next round until the number of rounds of the looping is reached. As mentioned above, for each round, a new subkey is to be generated. For example, in the second round of the looping, the KeyExpansion is performed to generate the third subkey based on the second subkey. The generation of the other subkeys is done in the same way. When the looping is completed, the ciphertext is obtained by processing the result of the looping through the SubBytes, ShiftRows, and AddRoundKey.
The AES system decrypts the ciphertext according to the following decryption algorithm.
Decryption Algorithm of AESAddRoundKeyfor round=1 to Nr−1InvKeyExpansionInvShiftRowsInvSubBytesInvMixColumnsAddRoundKeyend forInvShiftRowsInvSubBytesAddRoundKey
The operations in decryption are basically the inverse of the operations in encryption. The AES decryption includes the following steps. First, the inverse of AddRoundKey (InvAddRoundKey) is performed on the ciphertext and the previous subkey produced in the encryption above, for example, the 10th subkey that is assumed to be the last produced subkey after the encryption operation, and to output the result of the InvAddRoundKey, wherein the result of the InvAddRoundKey is referred to as decryption input ciphertext, for the sake of brevity. Note that since the InvAddRoundKey is identical to the AddRoundKey due to the characteristic of EX-OR operation, InvAddRoundKey is hereinafter referred to as AddRoundKey. Next, the following looping is performed. For each round of the looping, the inverse of KeyExpansion (InvKeyExpansion) is performed on an input subkey to produce an output subkey based on the input subkey, where the output subkey, in the encryption, is the immediately produced subkey before the input subkey produced. For example, in the first round, the InvKeyExpansion is applied to the 10th subkey (the input subkey) so as to produce the ninth subkey (the output subkey); in the second round, the application of InvKeyExpansion to the ninth subkey produces the eighth subkey; and so on. Next, the decryption input ciphertext is processed through the inverse of SubBytes (InvSubBytes), the inverse of ShiftRows (InvShiftRows), and the inverse of MixColumns (InvMixColumns). After that, AddRoundKey (i.e. InvAddRoundKey) is performed on the result of the last operation and the current subkey, resulting in the next decryption input ciphertext for the next round. The current key, for example, in the first round, is the ninth subkey after the application of InvKeyExpansion to the 10th subkey. Afterward, the looping is performed until the number of round of the looping is reached. The decryption result is finally obtained by processing the result from the rounds of the looping through the InvSubBytes, InvShiftRows, and AddRoundKey.
As described above, the AES algorithm has five main operations, namely, AddRoundKey, KeyExpansion, SubBytes, ShiftRows, and MixColumns. These operations will be described in the following. For the sake of brevity, hereinafter, the description employs several notations. (1) The output of one operation is denoted by “out” while the input of the operation is denoted by “in”. (2) The notation “+” (or “⊕”) denotes bitwise exclusive-OR operation (EX-OR) other than addition. Since the five main operations are performed sequentially during the encryption/decryption and the output of an immediate operation (out) is as the input of its successive operation (in), these outputs and inputs of these operations will be denoted, for the sake of brevity, by out's and in's only, without names particularly denoted for them. In addition, plaintexts, ciphertexts, and subkeys have data lengths of 128 bits and are represented by 4×4 matrices with elements of 8 bits.
FIG. 1 illustrates the effect of AddRoundKey on data. As mentioned above, the operation of AddRoundKey is bitwise exclusive-OR (EX-OR) operation. The EX-OR is performed on an input data code (in) and a subkey (k), resulting in an output data code (out). By the characteristic of EX-OR operation, the input data code (in) is equal to the EX-OR operation of the output data code (out) and the subkey (k). In FIG. 1, AddRoundKey is illustrated in terms of respective elements and is represented as inN ⊕kN=outN, where N is an integer indicative of the corresponding element's number. For the sake of brevity, this notation will hereinafter be adopted in the drawings.
FIG. 2 illustrates the effect of ShiftRows on data. In ShiftRows, the rows of an input data code (in), for example, the output of the AddRoundKey, is cyclically shifted to the right over different offsets. For example, the first row is not shifted (or shifted over zero byte), the second row is shifted to the right over one byte, the third row over two bytes, the fourth over three bytes and then the output of the ShifRows (out) is obtained as shown in the left of FIG. 2. If ShiftRows is in the way as in the example, the inverse of the ShiftRows (InvShiftRows) acts on its input data code in an inverse manner of the ShiftRows. That is, the first row of the input data code to InvShiftRows is not shifted (or shifted over zero byte), the second row is shifted to the left over one byte, the third over two bytes, and the fourth over three bytes.
FIG. 3 illustrates the effect of MixColumns/InvMixColumns on data. In MixColumns, every column of an input data code, e.g., obtained from the output of the ShiftRows, is transformed into the corresponding column of the output data code by the matrix multiplication of a specific multiplication matrix by the column. For example, the first column of the input data code (in) with elements in0, in1, in2, and in3 is multiplied by a 4×4 matrix in the upper of FIG. 3, resulting in the first column of the output of the MixColumns with elements out0, out1, out2, and out3. Conversely, the application of MixColumns to all columns of the output data code with the inverse of the specific multiplication matrix results in the input data code, e.g., as illustrated in the lower matrix multiplication. That is, InvMixColumns uses a specific multiplication matrix that is the inverse of the specific multiplication matrix for MixColumns.
FIG. 4 illustrates the effect of SubBytes/InvSubBytes on data. SubBytes is a non-linear byte substitution, operating on every byte of the input data code independently. The substitution table used in the substitution operation is called S-box, and the application of the S-box to each byte of the input data code (say x) results in one byte of data (say y). The operation of the S-box can be expressed as:y=M*multiplicative_inverse(x)+c,  (1)
where
  M  =                    (                                            1                                      1                                      1                                      1                                      1                                      0                                      0                                      0                                                          0                                      1                                      1                                      1                                      1                                      1                                      0                                      0                                                          0                                      0                                      1                                      1                                      1                                      1                                      1                                      0                                                          0                                      0                                      0                                      1                                      1                                      1                                      1                                      1                                                          1                                      0                                      0                                      0                                      1                                      1                                      1                                      1                                                          1                                      1                                      0                                      0                                      0                                      1                                      1                                      1                                                          1                                      1                                      1                                      0                                      0                                      0                                      1                                      1                                                          1                                      1                                      1                                      1                                      0                                      0                                      0                                      1                                      )            ⁢                          ⁢      and      ⁢                          ⁢      c        =                            [                                                    0                                            1                                            1                                            0                                            0                                            0                                            1                                            1                                              ]                T            .      
Since the multiplicative inverse (multiplicative_inverse) is a complicated function, the mostly used approach to SubBytes is to use a look-up table to obtain y from x. As shown in FIG. 4, in SubBytes, each element of the output data code, such as out0, is obtained from an element of the input data code, such as in0, through a look-up table, which is represented by y=Table_A(x). Table_A is indicative of the substitution table, i.e., the S-box of AES. Conversely, the application of InvSubBytes to every element obtained from the SubBytes, such as out1, results in the corresponding element of the input data code for the SubBytes, such as in0, through an inverse look-up table, which is represented by x=Table_B(y). Table_B is indicative of the inverse substitution table, i.e., the inverse S-box of AES (inv-S-box). In practice, S-box and inv-S-box require substantial hardware, making them not economic to be implemented.
In implementation of AES, several main difficulties should be overcome. As described above, each of the algorithms of AES encryption and decryption has different processing steps, wherein inverse operations and non-linear substitution operations are involved. Particularly, SubBytes and InvSubBytes, the non-linear substitution operations, require referring to respective look-up tables. The implementation of the substitution operations will occupy substantial memory space (e.g., 2×16×256×8 bits) under the design requirement for high efficient encryption/decryption. In addition, MixColumns and InvMixColumns involve matrix multiplication. If they are not to be integrated effectively, their implementation will also occupy a substantial amount of operating resource. Thus, in implementation, these operations should be considered and redesigned as so to lower the hardware complexity and save the operating resource.